package main.leetcode.clockin.October;

import java.util.Arrays;

/**
 * 75. 颜色分类
 *
 * <p>给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
 *
 * <p>此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
 *
 * <p>注意: 不能使用代码库中的排序函数来解决这道题。
 *
 * <p>示例: 输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2]
 *
 * <p>进阶：<br>
 * 一个直观的解决方案是使用计数排序的两趟扫描算法。 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。 <br>
 * 你能想出一个仅使用常数空间的一趟扫描算法吗？
 */
public class day7 {
    public static void main(String[] args) {
        int[] nums = {1, 0};
        new day7().sortColors(nums);
        System.out.println(Arrays.toString(nums));
    }

    public void sortColors(int[] nums) {
        if (nums == null || nums.length < 3) {
            return;
        }
        int n = nums.length;
        /*
        i：区间0的下标
        j：区间1的下标
        k：区间2的下标
         */
        int i = 0, j = 0, k = n - 1;
        while (j <= k) {
            if (nums[j] == 0) {
                exch(nums, i++, j++);
            } else if (nums[j] == 1) {
                ++j;
            } else if (nums[j] == 2) {
                exch(nums, j, k--);
            }
        }
    }

    private void exch(int[] nums, int i, int j) {
        nums[i] = nums[i] + nums[j] - (nums[j] = nums[i]);
    }
}
